package com.wang.violentrecursion;

/**
 * @Author: along
 * @Create: 2021/5/4
 * @Description:背包问题
 */
public class Demo05_Knapsack {

        public static int getMaxValue(int[] w, int[] v, int bag) {
            return process(w, v, 0, 0, bag);
        }
        //w[] 货物的重量 v[] 货物的价值 bag 背包容量 均不变
        //0...index - 1上进行选择（是否要该位置的货物），使得已经达到的重量为alreadyW
        // index... 最大价值
        //若返回-1，认为没有该方案
        //否则认为返回的是真实的价值（w和v都为正数）
        public static int process(int[] w, int[] v, int index, int alreadyW, int bag) {
            if (alreadyW > bag) {
                return -1;
            }
            // 重量没超，并且没有货物可选了，则maxValue为0
            if (index == w.length) {
                return 0;
            }
            //没要index的货物情况下，后续的最大价值
            int p1 = process(w, v, index + 1, alreadyW, bag);
            //要了index位置的货物
            int p2next = process(w, v, index + 1, alreadyW + w[index], bag);
            int p2 = -1;
            //如果后面的过程有效，则在要index货物的情况下v[index] + p2next（需要加上当前位置的价值）
            if (p2next != -1) {
                p2 = v[index] + p2next;
            }
            return Math.max(p1, p2);

        }

        public static int maxValue(int[] w, int[] v, int bag) {
            return process(w, v, 0, bag);
        }

        // 只剩下rest的空间了，
        // index...货物自由选择，但是rest不小于0
        // 返回index...货物能够获得的最大价值
        public static int process(int[] w, int[] v, int index, int rest) {
            //剩余空间为0 该方案无效
            if (rest < 0) { // base case 1
                return -1;
            }
            // rest >= 0 并且已经来到最后一件货物
            if (index == w.length) { // base case 2
                return 0;
            }
            // 不要index位置货物 则剩余容量不变
            int p1 = process(w, v, index + 1, rest);
            //要index位置货物，则剩余容量需减去index位置的w
            int p2next = process(w, v, index + 1, rest - w[index]);

            int p2 = -1;
            if (p2next != -1) {
                p2 = v[index] + p2next;
            }
            return Math.max(p1, p2);
        }
        //动态规划
        public static int dpWay(int[] w, int[] v, int bag) {
            int N = w.length;
            int[][] dp = new int[N + 1][bag + 1];//初始化dp
            //dp[N+1][bag+1] = 0 默认为0
            //第N行默认都为0，已经填好了
            for (int index = N - 1; index >= 0; index--) {//从N-1行往上填，一直到第一行
                for (int rest = 1; rest <= bag; rest++) {
                    dp[index][rest] = dp[index + 1][rest];
                    if (rest >= w[index]) {//判断rest-w[index]是否有效
                        dp[index][rest] = Math.max(dp[index][rest], v[index] + dp[index + 1][rest - w[index]]);
                    }
                }
            }
            return dp[0][bag];
        }

        public static void main(String[] args) {
            int[] weights = { 3, 2, 4, 7 };
            int[] values = { 5, 6, 3, 19 };
            int bag = 11;
            System.out.println(maxValue(weights, values, bag));
            System.out.println(dpWay(weights, values, bag));
            System.out.println(getMaxValue(weights,values,bag));
        }

}
